package com.datastructure.test.totalofrootandleaf;

import java.util.ArrayList;
import java.util.Collections;

public class TotalOfRootAndLeaf {

    ArrayList<ArrayList<Integer>> result=new ArrayList<>();

    public static void main(String[] args) {

    }

    public ArrayList<ArrayList<Integer>> pathSum (TreeNode root, int sum) {
        // write code here
        if(root==null){
            return result;
        }
        ArrayList<Integer> buffer = new ArrayList<>();
        dfs(root,0,buffer,sum);
        return result;
    }

    private void dfs(TreeNode root,int nowsum, ArrayList<Integer> buffer, int target) {
        if(target==(root.val+nowsum)&&root.right==null&&root.left==null){
            buffer.add(root.val);
            result.add(new ArrayList<>(buffer));
        }else {
            buffer.add(root.val);
        }
        if(root.left!=null){
            dfs(root.left,nowsum+root.val,buffer,target);
            buffer.remove(buffer.size()-1);
        }

        if(root.right!=null){
            dfs(root.right,nowsum+root.val,buffer,target);
            buffer.remove(buffer.size()-1);
        }
    }
}
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
}
